\documentclass[a4paper,10pt]{article}

%linguagem
\usepackage[brazil]{babel}
%encodificação
\usepackage[utf8]{inputenc}
%biblioteca de matemática
\usepackage{amssymb,amsmath}
%pacote para codigo fonte
\usepackage{listings}
%figuras
\usepackage{graphicx}
%cores
\usepackage{color}
%paragrafo no inicio da secao
\usepackage{indentfirst}
%url
\usepackage{framed, url}
\usepackage{fancyvrb}

%define a cor "claro"
\definecolor{claro}{gray}{0.9}

%configurações do listings
\lstset{frame=trBL, numbers=left, xleftmargin=0pt, xrightmargin=0pt,
breaklines=true, language=Java}

\begin{document}

\input{./titulo.tex}
\tableofcontents
\pagebreak

\section{Introdução}
O compilador é o programa responsável por transformar um código-fonte de uma
linguagem de programação em outra linguagem, geralmente um código binário, ou
executável. O processo de compilação é feito através de várias etapas, como
mostrado na figura \ref{fig:fases}. 

\begin{figure}[h] 
\centering
\includegraphics[scale=0.6]{imagens/fases.png} 
\label{fig:fases} 
\caption{Fases do processo de compilação} 
\end{figure}

O objetivo deste trabalho é implementar uma tabela de símbolos. Ela é uma
estrutura usada para auxiliar este processo, contendo informações sobre as
palavras encontradas no código-fonte. Ela é gerada de forma incremental, nas
fases de análise. As informações contidas numa tabela de símbolos podem variar,
mas geralmente contém características como o tipo (integer, real, boolean,
String, etc), a posição relativa na memória e o escopo.

\section{Desenvolvimento}
A tabela de símbolos pode ser implementada de várias formas. Algumas consagradas
são listas encadeadas, árvores binárias, tabelas de dispersão, e floresta de
árvores binárias. Neste trabalho a tabela de símbolos foi implementada usando
tabelas de dispersão (hashtables em inglês).

Uma tabela é usada para cada escopo do código-fonte. O nome de cada símbolo é
usado como chave para as hashtables. Junto com o nome, são armazenados o tipo, a
classe e o offset dos símbolos. Um exemplo da utilização desta estrutura seria:

\begin{Verbatim}[frame=single]
int x;
char y;
    {
    real x;
    }
char z;
\end{Verbatim}

A figura \ref{fig:tabelas} mostra a configuração da tabela de símbolos para o
exemplo de código acima.

\begin{figure}[h] 
\centering
\includegraphics[scale=0.6]{imagens/tabelas.png} 
\label{fig:tabelas} 
\caption{Estrutura da tabela de símbolos} 
\end{figure}

O programa foi dividido em 3 módulos:
\begin{itemize}
\item Simbolo.java: Contém a classe ``Símbolo''. Esta classe possui os atributos
e métodos necessários para a abstração dos símbolos.
\item Tabela.java: Contém a implementação da tabela de símbolos.
\item ExisteException.java: Exceção que é lançada quando o programa tenta
declarar dois símbolos com o mesmo nome no mesmo escopo.
\end{itemize}

Todo o trabalho foi implementado usando a linguagem Java. O código-fonte pode
ser encontrado na seção \ref{sec:codigo}.

\section{Testes}

Os testes foram elaborados para abranger várias situações de uso da tabela de
símbolos. Eles estão no formato:

\begin{itemize}
\item Pseudo-código: Exemplo de código fonte.
\item Teste.java: Método ``main''.
\item Saída: Tabela de símbolos resultante.
\end{itemize}

\subsection{Teste 1}

Este teste avalia se a tabela de símbolos está inserindo os símbolos e definindo
seus atributos corretamente.

Pseudo-código:
\begin{Verbatim}[frame=single]
prog teste{
    int x;
    char y;
    func f(){
        real x;
    }
    char z;
}
\end{Verbatim}

Teste.java:
\begin{lstlisting}

public class Teste {
    public static void main(String[] args) throws ExisteException {

        Tabela tabela = new Tabela();

        tabela.add(new Simbolo("teste","-","prog"));
        tabela.sobeNivel();
        tabela.add(new Simbolo("x","int","var"));
        tabela.add(new Simbolo("y","char","var"));
        tabela.add(new Simbolo("f","-","func"));
        tabela.sobeNivel();
        tabela.add(new Simbolo("x","real","var"));
        tabela.printTabela();
        tabela.desceNivel();
        tabela.add(new Simbolo("z","char","var"));
        tabela.printTabela();
        tabela.desceNivel();
        tabela.printTabela();
        tabela.desceNivel();

    }
}

\end{lstlisting}

Saída:
\begin{Verbatim}[frame=single]

***********
|Nivel 2  |
***********

Nome: x
Tipo: real
Classe: var

***********
|Nivel 1  |
***********

Nome: x
Tipo: int
Classe: var

Nome: f
Tipo: -
Classe: func

Nome: z
Tipo: char
Classe: var

Nome: y
Tipo: char
Classe: var

***********
|Nivel 0  |
***********

Nome: teste
Tipo: -
Classe: prog

\end{Verbatim}

\subsection{Teste 2}

Este teste avalia a capacidade da tabela de símbolos de criar e remover escopos.

\begin{Verbatim}[frame=single]
prog teste2{
    int a;
    {
        int a;
    }
    {
        int a;
    }
}
\end{Verbatim}

Teste.java:
\begin{lstlisting}

public class Teste {
    public static void main(String[] args) throws ExisteException {

        Tabela tabela = new Tabela();

        tabela.add(new Simbolo("teste2","-","prog"));
        tabela.sobeNivel();
        tabela.add(new Simbolo("a","int","var"));
        tabela.sobeNivel();
        tabela.add(new Simbolo("a","int","var"));
		tabela.printTabela();
		tabela.desceNivel();
		tabela.sobeNivel();
        tabela.add(new Simbolo("a","int","var"));
		tabela.printTabela();
		tabela.desceNivel();
        tabela.printTabela();
        tabela.desceNivel();
        tabela.printTabela();
        tabela.desceNivel();

    }
}

\end{lstlisting}

Saída:
\begin{Verbatim}[frame=single]
***********
|Nivel 2  |
***********

Nome: a
Tipo: int
Classe: var

***********
|Nivel 2  |
***********

Nome: a
Tipo: int
Classe: var

***********
|Nivel 1  |
***********

Nome: a
Tipo: int
Classe: var

***********
|Nivel 0  |
***********

Nome: teste2
Tipo: -
Classe: prog

\end{Verbatim}

\subsection{Teste 3}

Este teste avalia se a tabela de símbolos está cumprindo sua função de alertar
sobre a declaração de símbolos com o mesmo nome em um mesmo escopo.

Pseudo-código:
\begin{Verbatim}[frame=single]
prog teste2{
    int a;
    {
        int a;
        int a;
    }
}
\end{Verbatim}

Teste.java:
\begin{lstlisting}

public class Teste {
    public static void main(String[] args) throws ExisteException {

        Tabela tabela = new Tabela();

        tabela.add(new Simbolo("teste2","-","prog"));
        tabela.sobeNivel();
        tabela.add(new Simbolo("a","int","var"));
        tabela.sobeNivel();
        tabela.add(new Simbolo("a","int","var"));
        tabela.add(new Simbolo("a","int","var"));
        tabela.printTabela();
        tabela.desceNivel();
        tabela.printTabela();
        tabela.desceNivel();
        tabela.printTabela();
        tabela.desceNivel();

       
    }
}

\end{lstlisting}

Saída:
\begin{Verbatim}[frame=single]
Exception in thread "main" compiladores.ExisteException: 
A variavel "a" ja foi declarada neste escopo!!
	at compiladores.Tabela.add(Unknown Source)
	at Teste.main(Unknown Source)
\end{Verbatim}

\section{Conclusão}

O desenvolvimento deste trabalho possibilitou o aprendizado acerca do
funcionamento da tabela de símbolos. A implementação foi facilitada pela grande
quantidade de código e algoritmos prontos que puderam ser reaproveitados, como
as hashtables da linguagem Java. O programa foi desenvolvido de forma modular,
para favorecer o uso do mesmo nas outras etapas da construção de um compilador.

\section{Código-fonte}
\label{sec:codigo}

\subsection{Simbolo.java}

\begin{lstlisting}[xleftmargin=-80px,xrightmargin=-80px]
package compiladores;
import java.io.*;

public class Simbolo{
	private String nome_;
	private String tipo_;
	private String classe_;
	private int offset_;

	public Simbolo(String nome, String tipo, String classe){
		this.nome_ = nome;
		this.tipo_ = tipo;
		this.classe_ = classe;
		this.offset_ = 4;
	}

	public void printSimbolo(){
		System.out.println("Nome: "+this.nome_);
		System.out.println("Tipo: "+this.tipo_);
//		System.out.println("Offset: "+this.offset_);
		System.out.println("Classe: "+this.classe_);
	}

	public String getNome(){
		return this.nome_;
	}

	public String getTipo(){
		return this.tipo_;
	}
	public int getOffset(){
		return this.offset_;
	}
	public String getClasse(){
		return this.classe_;
	}

}
\end{lstlisting}

\subsection{Tabela.java}
\begin{lstlisting}[xleftmargin=-80px,xrightmargin=-80px]

package compiladores;
import java.util.*;
import java.io.*;

public class Tabela {
	
	private final static int NMAX = 10;
	private Hashtable[] tabelas = new Hashtable[NMAX];
	private int nivel;

	public Tabela() {
		nivel = 0;
		for(int i = 0;i<NMAX;i++)
			tabelas[i] = new Hashtable();
	}

	public void sobeNivel(){
		nivel++;
	}

	public void desceNivel(){
		tabelas[nivel].clear();
		nivel--;
	}

	public int getNivel(){
		return nivel;
	}
	public void add(Simbolo s) throws ExisteException {
		if(tabelas[nivel].get(s.getNome())==null)
			tabelas[nivel].put(s.getNome(),s);
		else
			throw new ExisteException("A variavel \""+s.getNome()+"\" ja foi declarada neste escopo!!");
	}

	public Simbolo lookup(String s) {
		
		for(int i=nivel; i>=0 ;i--)
			if(tabelas[i].get(s)!=null)
				return (Simbolo)(tabelas[i].get(s));
		
		return null;
	}

	public void printTabela(){
		if(tabelas[nivel].size() != 0){
			System.out.println("***********");
			System.out.println("|Nivel "+nivel+"  |");
			System.out.println("***********\n");
			Enumeration e = tabelas[nivel].elements();
			while(e.hasMoreElements()){
				((Simbolo)e.nextElement()).printSimbolo();
				System.out.println();
			}
		}
	}
}

\end{lstlisting}

\subsection{ExisteException.java}

\begin{lstlisting}[xleftmargin=-80px,xrightmargin=-80px]

package compiladores;

public class ExisteException extends Exception {
	public ExisteException(String s){
		super(s);	
	}	
}
\end{lstlisting}

\begin{thebibliography}{99}
\bibitem{wiki} \url{http://en.wikipedia.org/wiki/Compiler}
\bibitem{artigo} \url{https://homepages.dcc.ufmg.br/~mariza/Cursos/CompiladoresI/Artigos/TabSimb.pdf}
\bibitem{api} \url{http://java.sun.com/javase/6/docs/api/index.html?overview-summary.html}
\bibitem{slides} \url{https://homepages.dcc.ufmg.br/~mariza/Cursos/CompiladoresI/Geral/Slides/SlidesPagComp/compTranspGrad.html}
\bibitem{livro} Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, \emph{Compilers - Principles Techniques and Tools}, 2006
\end{thebibliography}

\end{document}
